TNotes.algorithms

Appearance

0003. 动态规划算法

0003. 动态规划算法 ​

1. 🎯 本节内容 ​

  • 动态规划算法

2. 🫧 评价 ​

记住一句话 👉 DP 的核心是：“将复杂问题分解为相互重叠的子问题，通过存储子问题的解来避免重复计算，从而高效地求解原问题。”只要遇到动态规划的问题，就想想这句话。

动态规划算法和分治算法很像，可以将动态规划算法理解为是：“带备忘录的”分治算法。

3. 🤔 动态规划算法是什么？ ​

动态规划 - Dynamic Programming - 简称 DP。

DP 算法思想的核心可以概括为一句话：“将复杂问题分解为相互重叠的子问题，通过存储子问题的解来避免重复计算，从而高效地求解原问题。”

“分而治之 + 记忆优化 = 动态规划”

可以把动态规划想象成：“聪明地记笔记” —— 遇到以前做过的题，不重新算，直接翻笔记，省时省力。

它不是一种具体的算法，而是一种解决问题的策略思想，特别适用于具有最优子结构和重叠子问题性质的最优化问题。

4. 🤔 DP 算法的两个核心要素是什么？ ​

4.1. 最优子结构（Optimal Substructure） ​

  • 原问题的最优解可以通过其子问题的最优解构造出来。
  • 也就是说，如果一个问题的最优解包含了子问题的最优解，则该问题具有最优子结构性质。
  • 保证我们可以“自底向上”或“递归地”构建全局最优解。

4.2. 重叠子问题（Overlapping Subproblems） ​

  • 在求解过程中，某些子问题会被多次重复计算。
  • 动态规划通过 记忆化（Memoization） 或 表格填表（Tabulation） 的方式，将已求解的子问题结果保存起来，下次直接复用，避免重复计算。
  • 这是动态规划相较于普通递归效率提升的关键 —— 空间换时间，用存储空间换取指数级的时间节省。

5. 🤔 动态规划的解题套路是说明？ ​

  1. 定义状态：明确 dp[i] 或 dp[i][j] 代表什么含义
  2. 找出状态转移方程：建立当前状态与之前状态的关系（核心公式）
  3. 确定初始条件（边界）：dp 数组的起始值
  4. 确定计算顺序：自底向上（迭代）或记忆化递归
  5. 返回结果：根据题目要求，从 dp 数组中提取最终答案

6. 🤔 LeetCode 上对应的算法题有哪些？ ​

7. 🔗 引用 ​

Discussions